package com.squirrel.michale;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/8 10:47 AM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode2530_3 {

    public long maxKelements(int[] nums, int k) {
        for (int i = 0; i < nums.length; i++) {
            heapInsert(nums,i);
        }

        long sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[0];
            nums[0] = (nums[0] + 2) / 3;
            heapify(nums,0, nums.length);
        }
        return sum;
    }
    private void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    private void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


    public static void main(String[] args) {

        LeetCode2530_3 leetCode2530 = new LeetCode2530_3();

        int[] nums = new int[]{10,10,10,10,10};
        int k = 5;
        System.out.println(leetCode2530.maxKelements(nums, k));


        int[] nums2 = new int[]{1,10,3,3,3};
        int k2= 3;
        System.out.println(leetCode2530.maxKelements(nums2, k2));

    }

}
